package writtenTraining.day45;

import java.util.*;

/**
 * day45(1)：模拟 + 滑动窗口：kanan和高音
 */


public class Main {
    public static void main(String[] args) {
//         模拟 + 滑动窗口
//         输入数据
            Scanner in = new Scanner(System.in);
            int n = in.nextInt();
        int[] nums = new int[n];
        for(int i =0; i < n; i++) {
            nums[i] = in.nextInt();
        }        
        
        int ret = -0x3f3f3f3f;
        for(int left = 0, right = 1; right < n; right++) {
            // 出窗口
            if(nums[right] - nums[right - 1] > 8) {
                left = right;
            }
            
            // 更新结果
            ret = Math.max(ret,right - left + 1);
        }
        
//         输出结果
        System.out.println(ret);
    } 
}


/**
 * day45(2):bfs + 最短步数 + 最短步数的次数维护:MT3 拜访
 */

 class Solution1 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型二维数组
     * @param n int整型
     * @param m int整型
     * @return int整型
     */
    public int countPath (int[][] nums, int n, int m) {
        // bfs + 最短步数 + 最短步数的次数维护

        Queue<int[]> queue = new LinkedList<>();
        int[][] dest = new int[n][m];
        int[][] cnt = new int[n][m];
        // 寻找经理位置
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(nums[i][j] == 1) {
                    queue.add(new int[]{i,j});
                    dest[i][j] = 0;
                    cnt[i][j] = 1;
                } else {
                    dest[i][j] = -1;
                }

            }
        }

        int ret = 0;
        int[] dx = {0,0,-1,1};
        int[] dy = {-1,1,0,0};
        boolean[][] vim = new boolean[n][m];
        while(!queue.isEmpty()) {
            ret++;
            int sz = queue.size();
            for(int i =0; i< sz; i++) {
                int[] index = queue.poll();
                int r = index[0], l = index[1];
                for(int k = 0; k < 4; k++) {
                    int x = r + dx[k];
                    int y = l + dy[k];

                    if(x >= 0 && x < n
                            && y >= 0 && y < m &&
                            nums[x][y] != -1 ) {
                        if (dest[x][y] == -1) {
                            queue.add(new int[]{x,y});
                            // 更新步数
                            dest[x][y] = dest[r][l] + 1;
                            // 加前面的次数
                            cnt[x][y] += cnt[r][l];
                        } else if(dest[r][l] + 1 == dest[x][y]) {
                            // 加前面的次数
                            cnt[x][y] += cnt[r][l];
                        }

                    }
                }
            }
        }

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(nums[i][j] == 2) {
                    return cnt[i][j];
                }

            }
        }
        return 0;
    }
}


/**
 * day45:(3)动态规划 + 股票问题 + 状态基:DP33 买卖股票的最好时机(四)
 */

 class Main1 {
    public static void main(String[] args) {
        // 动态规划 + 股票问题 + 状态基
        // 输入数据
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), k = in.nextInt();

        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i]  = in.nextInt();
        }

        // 卖出dp
        int INF = 0x3f3f3f3f;
        int[][] dp = new int[n][k + 1];
        // 买入gp
        int[][] gp = new int[n][k + 1];

        // 初始化
        for (int j = 1 ; j <= k ; j++) {
            dp[0][j] = -INF;
            gp[0][j] = -INF;
        }
        gp[0][0] = -nums[0];

        int ret = -INF;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= k; j++) {
                // 继承上一次交易的卖出利润
                // 卖出的时候一定要注意k + 1
                dp[i][j] = dp[i - 1][j];
                if (j - 1 >= 0) {
                    // 防止越界
                    dp[i][j] = Math.max(dp[i - 1][j]
                            , gp[i - 1][j - 1] + nums[i]);
                }


                // 买入的状态
                // 继承时交易次数相同
                // 交易次数和前一天相同
                gp[i][j] = Math.max(gp[i - 1][j]
                        , dp[i - 1][j] - nums[i]);
            }

        }

        // 最终结果有可能 0~1 之间的最大利润
        for(int j = 0; j <=k; j++) {
            ret = Math.max(ret,dp[n-1][j]);
        }
        System.out.println(ret);
    }
}